package com.leetcode.offer;

import sun.security.x509.CRLNumberExtension;

/**
 * @author zfl
 * @Classname FindNumberIn2DArray
 * @Description 二维数组中的查找
 * @Date 2020/10/14 14:39
 */
public class FindNumberIn2DArray {

    /**
     * @param matrix
     * @param target
     * @return 暴力法
     * 执行用时：1 ms, 在所有 Java 提交中击败了16.32%的用户
     * 内存消耗：44.4 MB, 在所有 Java 提交中击败了78.08%的用户
     */
    public static boolean findNumberIn2DArray1(int[][] matrix, int target) {
        // 注意考虑特殊情况
        /*if(matrix == null || matrix.length == 0) {
            return false;
        }
        if(matrix[matrix.length - 1].length == 0) {
            return false;
        }*/
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int left = 0, right = 0,mid = 0;
        for (int i = 0; i < matrix.length; i++) {
            // 这里应该设置为 matrix[i][0] <= target
            if(matrix[i][0] <= target) {
                left = 0;
                right = matrix[i].length - 1;
                while (left <= right) {
                    mid = left + (right - left) / 2;
                    if(matrix[i][mid] < target) {
                        left = mid + 1;
                    }else if(matrix[i][mid] > target) {
                        right = mid - 1;
                    }else {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * @param matrix
     * @param target
     * @return 线性查找法，又称标志位法
     * 由于给定二维数组具备每行从左到右递增以及每列从上往下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。
     * 从二维数组的右上角开始查找，如果当前元素等于目标值，返回true，如果小于目标值，则移动到下边一行，如果大于目标值，则左移一列。
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：44.4 MB, 在所有 Java 提交中击败了79.73%的用户
     */
    public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = 0,column = matrix[0].length - 1;
        while (row <= matrix.length - 1 && column >= 0) {
            if(matrix[row][column] == target) {
                return true;
            }else if(matrix[row][column] < target) {
                row++;
            }else if(matrix[row][column] > target) {
                column--;
            }
        }
        return false;
    }
}
